﻿/*
题目: 移掉 K 位数字

给你一个以字符串表示的非负整数 num 和一个整数 k ，移除这个数中的 k 位数字，使得剩下的数字最小。请你以字符串形式返回这个最小的数字。

https://leetcode.cn/problems/remove-k-digits/
*/

#include <iostream>
#include <random>
#include <string>
#include <vector>
#include <list>
#include "TreeNode.hpp"
#include "ListNode.hpp"
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <functional>

using namespace std;

class Solution {
public:
    // 贪心 + 单调栈, "123" 一定比 "143" 小，弹出大的，让小的变到前面
    string removeKdigits(string num, int k) {
        stack<int> incr;        // 单调递增栈

        for (int i = 0; i < num.size(); i++) {
            while (!incr.empty() && num[incr.top()] > num[i] && k) {
                incr.pop();
                k--;
            }

            incr.push(i);
        }
        // 弹出最后那几个
        while (k-- > 0) {
            incr.pop();
        }

        string res;
        while (!incr.empty()) {
            res.push_back(num[incr.top()]);
            incr.pop();
        }
        while (res.size() > 1 && res.back() == '0')     res.pop_back();

        std::reverse(res.begin(), res.end());

        return res.size() == 0 ? "0" : res;
    }
};
